package backtrack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 将这道题转化为子集问题
 * 找出nums（可能有重复项）的所有子集，判断这个子集中的数加起来是不是等于target
 * 是的话加入集合
 */
public class Solution40 {
    List<Integer> track = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTrack(candidates,target,0,0);
        return result;
    }

    public void backTrack(int[] candidates,int target,int targetSum,int start){
        //targetSum记录一下每个结点所有元素的总和

        if (target==targetSum){
            //你都等于targetSum了，也没有往后遍历的必要了，再往后也是把targetSum变大
            result.add(new ArrayList<>(track));
            return;
        }

        if (targetSum > target){
            //你一进来都比target大了，也没有往后面遍历的必要了，再往后也是变大。
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            //做出选择

            //当前元素与上一个元素重合，我们做剪枝
            if (i > start && candidates[i-1]==candidates[i]){
                continue;
            }
            targetSum += candidates[i];
            track.add(candidates[i]);

            backTrack(candidates, target, targetSum, i+1);

            //撤销选择
            targetSum -= candidates[i];
            track.remove(Integer.valueOf(candidates[i]));
        }
    }
}
